/*
 * @lc app=leetcode.cn id=23 lang=typescript
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
class Node {
    val: any
    priority: any
    constructor(val: any, priority: any) {
        this.val = val;
        this.priority = priority;
    }
}
// 优先队列（最小堆）
class PriorityQueue {
    values: any
    constructor() {
        this.values = [];
    }

    enqueue(val: any, priority: any) {
        let node = new Node(val, priority);
        this.values.push(node);
        this.bubbleUp();
    }

    dequeue() {
        let max = this.values[0];
        let end = this.values.pop();
        if (this.values.length) {
            this.values[0] = end;
            this.bubbleDown();
        }
        return max.val;
    }

    isEmpty() {
        return !this.values.length;
    }

    bubbleUp(index = this.values.length - 1) {
        if (index <= 0) return;
        let parentIndex = Math.floor((index - 1) / 2);
        if (this.values[index].priority <= this.values[parentIndex].priority) {
            [this.values[index], this.values[parentIndex]] = [this.values[parentIndex], this.values[index]];
            this.bubbleUp(parentIndex);
        }
    }

    bubbleDown(index = 0, swapIndex: any = null) {
        let leftIndex = index * 2 + 1,
            rightIndex = index * 2 + 2,
            length = this.values.length;

        if (leftIndex < length) {
            if (this.values[leftIndex].priority <= this.values[index].priority) {
                swapIndex = leftIndex;
            }
        }

        if (rightIndex < length) {
            if ((swapIndex === null && this.values[rightIndex].priority <= this.values[index].priority) || (swapIndex !== null && this.values[rightIndex].priority <= this.values[leftIndex].priority)) {
                swapIndex = rightIndex;
            }
        }

        if (swapIndex !== null) {
            [this.values[index], this.values[swapIndex]] = [this.values[swapIndex], this.values[index]];
            this.bubbleDown(swapIndex, null);
        }
    }
};

//  思路：
//  利用好优先队列维护当前每个（k个）链表没有被合并的元素的最前面一个
//  在 k 个元素里面选取 val 属性最小的元素合并到答案中

//  复杂度：O(kn × logk) 
//  优先队列插入和删除O(logk) 最多kn个点 O(k)

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    let queue = new PriorityQueue();
    lists.forEach(list => {
        // 把所有链表中的头节点存入优先队列
        if (list) queue.enqueue(list, list.val)
    });

    let res = new ListNode(-1);
    let curr: any = res;

    while (!queue.isEmpty()) {
        // 当前节点的下一个就是出队的节点
        curr.next = queue.dequeue();
        // 指针后移
        curr = curr.next;
        // 将出队链表的下一个节点入队
        if (curr.next) queue.enqueue(curr.next, curr.next.val);
    }
    return res.next;
};
// @lc code=end

import { ListNode } from './type'
let l1 = new ListNode(1, new ListNode(2, new ListNode(4)))
let l2 = new ListNode(1, new ListNode(3, new ListNode(4)))
let l3 = new ListNode(2, new ListNode(5, new ListNode(7)))
console.log(ListNode.printList(mergeKLists([l1, l2, l3])));
